package com.love.labuladong.str;

import java.util.Arrays;

/**
 * @Author : zh
 * @Description : 最短循环节的长度
 *
 * 给你一个字符串s,它一定是某个循环节不断自我连接形成的
 * 题目保证至少重复 2 次，但是最后一个循环节不一定完整
 * 现在想知道s的最短循环节是多长
 *结论  res = s.length - s的最长前后缀长度
 *
 * @Date : 2024-08-26 14:35
 */
public class Kmp_Each {


    public static void main(String[] args) {
        String s = "abcdeabcdeabc";
        int n = s.length();
        int[] ints = nextArray(s.toCharArray(),n);

        System.out.println(Arrays.toString(ints));

        int res = n - ints[n];
        System.out.println(res);

    }

    public static int[] nextArray(char[] s,int n){
        if(n == 1){
            return new int[]{-1};
        }
        int[] next = new int[n + 1];
        next[0] = -1;
        next[1] = 0;
        int i = 2,cn = 0;
        while (i <= n){
            if(s[i-1] == s[cn]){
                next[i++] = ++cn;
            }else if(cn > 0){
                cn = next[cn];
            }else {
                next[i++] = 0;
            }
        }
        return next;
    }

}
